package leetcode_jz_offer.day8_dp;

/**
 * @author 美女
 * @date 2022/07/17 13:18
 **/
public class Num10II_青蛙跳台阶 {
    public int numWays(int n) {
        final int MOD = 1000000007;
        //n=0是1种；n=1 1;n=2 2
        if(n==0||n==1){
            return 1;
        }
        int first=1;
        int second=1;
        int third=1;
        for(int i=2;i<=n;i++){
            third=first+second;
            third%=MOD;
            first=second;
            second=third;
        }
        return third;
    }
}
